Overview

LP

Primal (P), where x∈ℝnx \in \mathbb{R}^n:

minimizecTxsubject toAx=bx≥0\begin{aligned} & \text{minimize} & & c^T x \\ & \text{subject to} & & Ax = b \\ & & & x \geq 0 \end{aligned}

Lagrangian:

L(x,λ,ν)=cTx−λTx+νT(Ax−b)=(c−λ+ATν)x−bTν L(x,\lambda,\nu)=c^T x - \lambda^T x + \nu^T (Ax-b) = (c-\lambda+A^T \nu)x-b^T \nu

Lagrange dual function (LDF):

g(λ,ν)=infx⁡L(x,λ,ν)={−bTνif c−λ+ATν=0−∞otherwiseg(\lambda,\nu) = \inf_x L(x,\lambda,\nu)=\begin{cases} -b^T \nu \quad \text{if } c-\lambda + A^T \nu = 0 \\ -\infty \quad \text{otherwise}\end{cases}

Lagrange dual problem (LDP):

supλ≥0⁡g(λ,ν)≡\sup_{\lambda \geq 0} g(\lambda,\nu) \equiv max⁡bTysubject toATy+λ=cλ≥0 \begin{aligned} & \max & & b^T y \\ & \text{subject to} & & A^T y + \lambda = c \\ & & & \lambda \geq 0 \end{aligned}

where λ\lambda is the dual slack variable, transforming ATy≤cA^T y \leq c into an equality.

Dual (D):

max⁡bTysubject toATy≤c \begin{aligned} & \max & & b^T y \\ & \text{subject to} & & A^T y \leq c \end{aligned}

References:

  1. https://www.cs.princeton.edu/courses/archive/fall18/cos521/Lectures/lec17.pdf